import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/31 15:19
 * @description 思路：优化队列，维护k个最小的数，堆顶为最大值
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k, (a, b) -> {
            return b - a;
        });
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i * n + j + 1 <= k) {
                    pq.add(matrix[i][j]);
                }else {
                    if (pq.peek() > matrix[i][j]) {
                        pq.poll();
                        pq.add(matrix[i][j]);
                    }
                }
            }
        }
        return pq.peek();
    }
}
